package offer;

import java.util.ArrayList;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * @Author SSK
 * @Date Created in 23:39 2019/8/7
 * @Description 把二叉树打印成多行
 * @Version 1.0
 */
public class T61 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

    }
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
        if (pRoot==null) {
            return lists;
        }
        Queue<TreeNode> queue1 = new LinkedBlockingQueue<TreeNode>();
        queue1.add(pRoot);
        Queue<TreeNode> queue2 = new LinkedBlockingQueue<TreeNode>();
        while (!queue1.isEmpty()||!queue2.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            if (queue2.isEmpty()) {
               while (!queue1.isEmpty()) {
                   TreeNode node = queue1.poll();
                   list.add(node.val);
                   if (node.left!=null) {
                       queue2.add(node.left);
                   }
                   if (node.right!=null) {
                       queue2.add(node.right);
                   }

               }
            }else {
                while (!queue2.isEmpty()) {
                    TreeNode node = queue2.poll();
                    list.add(node.val);
                    if (node.left!=null) {
                        queue1.add(node.left);
                    }
                    if (node.right!=null) {
                        queue1.add(node.right);
                    }

                }

            }
            lists.add(list);
        }
        return lists;
    }
}
